package com.zk.algorithm.linkedlist;

import com.zk.algorithm.bean.ListNode;

/**
 * @author zk
 */
public class QuickSortList {

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        // 三个指针，左、右、中
        ListNode left = new ListNode(0),
                leftHead = left;
        ListNode right = new ListNode(0),
                rightHead = right;
        ListNode mid = new ListNode(0),
                midHead = mid;

        int val = head.val;

        // -1 -> 5 -> 3 -> 4 -> 0
        //  ↑
        //  m
        //       ↑
        //       l
        while (head != null) {
            if (head.val < val) {
                left.next = head;
                left = head;
            } else if (head.val > val) {
                right.next = head;
                right = head;
            } else if (head.val == val) {
                mid.next = head;
                mid = head;
            }

            head = head.next;
        }

        left.next = null;
        right.next = null;
        mid.next = null;

        return concat(sortList(leftHead.next), midHead.next, sortList(rightHead.next));
    }

    public ListNode concat(ListNode left, ListNode mid, ListNode right) {
        ListNode LeftTail = getTail(left);
        ListNode midTail = getTail(mid);
        midTail.next = right;
        if (LeftTail != null) {
            LeftTail.next = mid;
            return left;
        } else {
            return mid;
        }
    }

    public ListNode getTail(ListNode head) {
        if (head == null) return head;

        while (head.next != null)
            head = head.next;

        return head;
    }

}
